package day24_1590;

import java.util.HashMap;

/**
 * @ClassName Solution
 * @Description TODO
 * @Author clockTown
 * @Date 2021/6/2 18:41
 * @Version 1.0
 */
public class Solution {
    public static int minSubarray(int[] nums, int k) {

        //tar为数组总和sum取模k后得到的值，这里使用tar先得到总和，减少了变量的使用
        int tar = 0;
        for (int num : nums) {
            tar += num;
        }

        tar = Math.floorMod(tar, k);

        //使用map保存前缀和对应的余数
        HashMap<Integer, Integer> map = new HashMap<>();

        //TODO 应对从数组索引 0 处开始取子数组的情况？
        map.put(0, -1);

        //prefix为前缀和，res为当前数组长度
        int prefix = 0, res = nums.length;

        for (int i = 0; i < nums.length; i++) {

            prefix += nums[i];

            //计算前缀和取模k
            int mod = Math.floorMod(prefix, k);
            map.put(mod, i);

            //计算推导公式的左半部分
            //一边加一边取模可以减少时间复杂度，防止超时(大数取模会超时)
            if (map.containsKey(Math.floorMod(prefix - tar, k)))
                res = Math.min(res, i - map.get(Math.floorMod(prefix - tar, k)));

        }

        return res == nums.length ? -1 : res;

    }

    public static void main(String[] args) {
        int[] nums = {3, 1, 4, 2};
        int k = 6;
        System.out.println(minSubarray(nums, k));
    }
}
